effectively decidable

Definition

Given a set $D$, and subset $S \subseteq D$, $S$ is effectively decidable iff there is an effective procedure which, when given an object $x \in D$, will eventually answer "yes" if $x \in S$, and will eventually answer "no" if $x \notin S$.

Note: procedure eventually halts for any input $x$

Notes

• if there is some TM that accepts every string in language $L$ and either rejects or loops every string not in $L$, then $L$ semi-decidable or completely enumerable

See also

• effectively computable
• effectively enumerable
• decision problem

References

1. N. D. Jones, Computability and complexity: from a programming perspective. in Foundations of computing. Cambridge, Mass: MIT Press, 1997, p. 13.
2. https://www.cs.ox.ac.uk/people/paul.goldberg/FCS/slides3.pdf